package Array_and_String;

/*
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start i, end i] 。
请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/array-and-string/c5tv3/
 */

import java.util.ArrayList;
import java.util.Arrays;

public class _13合并区间 {
    public static void main(String[] args) {

        int[][] n = {{1,3},{2,6},{8,10},{15,18}};

        int[][] merge = merge(n);
        System.out.println(Arrays.deepToString(merge));

    }

    public static int[][] merge(int[][] intervals) {
        //排除空数组情况
        if (intervals == null || intervals.length == 0) {
            return new int[0][2];
        }

        //先将原二维数组根据区间左端点进行排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        //创建合并区间对象
        ArrayList<int[]> res = new ArrayList<>();

        //根据区间右端点进行合并
        //遍历数组
        for (int i = 0; i < intervals.length; i++) {
            //创建区间左右端点对象
            int left = intervals[i][0], right = intervals[i][1];
            //判断left是否与之前区间重合
            if (res.size() == 0 || intervals[i][0] > res.get(res.size() - 1)[1]) {
                //不重合 或初始res集合为空
                res.add(new int[]{left, right});
            } else {
                //重合
                //判断哪个区间右端点更大,更改重合区间右端点
                res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], right);
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}
